package 动态规划;

/**
 * @author 帅小伙
 * @date 2021/12/22
 * @description
 * 描述
 * 有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
 *
 * 现在给一串数字，返回有多少种可能的译码结果
 * 数据范围：字符串长度满足 0 < n \le 900<n≤90
 * 进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class Demo01 {

    public static void main(String[] args) {

    }


    public int solve (String nums) {
        // write code here

        int l = nums.length();
        char[] chars = nums.toCharArray();
        if(l<0 || chars[0]=='0'){
            return 0;
        }
        int dp[] = new int[l+1];
        dp[0] = 1;

        for (int i = 1; i <= l; i ++){
            char c = chars[i-1];
            if(c != '0'){
                dp[i] = dp[i-1];
            }
            if(i-2 >= 0){
                int val = Integer.valueOf(nums.substring(i-2,i));
                if(val >=10 && val <= 26){
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[l];
    }
}
